package array.removeElement;

/**
 * 题目: 给你一个数组nums和一个值 val，你需要原地移除所有数值等于 val 的元素。
        元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
        假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
        更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
        返回 k。

 * 注意: 数组中的元素实际上是不可以删除的，只能覆盖，所以原来的数组长度实则不变
 */


// 以下方法为暴力解法
// 两层for循环，外层循环找到要删除的元素，内层循环将后面的元素覆盖到当前位置
//时间复杂度：O(n*n)
/**
 * public class removeElement {
    public int removeElement(int[] nums, int val) {
        int res=nums.length;

        //外层循环,找到要删除的元素
        for (int i = 0; i <=res-1 ; i++) {
            if(nums[i]==val){
                //内层循环,将后面的元素覆盖到当前位置
                for(int j = i+1; j <=res-1; j++){
                    nums[j-1]=nums[j];
                }
                res--;
                i--;// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
            }

        }
        return res;
    }

}*/

/**
 * 优化方法: 双指针法（快慢指针法）：
            通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

                   位置               适用场景                     适用问题
 * 知识点: 双指针位置适合一个头，一个尾	有序数组，找最大/最小值	O(n)	sortedSquares、两数之和（有序数组）
                  适合两个头          滑动窗口、快慢指针	   O(n)	    去重、链表环检测、最小子数组

 * 快指针:获取新数组中的元素
 * 慢指针:获取新数组中需要更新的位置
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */

public class removeElement {
    public int removeElement(int[] nums, int val) {
        int slow=0;//慢指针
        int fast=0;//快指针

        for (; fast <= nums.length-1 ; fast++) {
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
}


